<?php
//include_once("class_segment.php");
//include_once("class_unit.php");
//include_once("inc_str.php");
//include_once("inc_array.php");

class suffixarray{
 private $array_str=array();
 private $array_suffix=array();
 private $array_repeated=array();
 private $array_distrib=array();
 private $array_distrib2=array();

 public function __construct(){}

 public function __get_array_str(){return $this->array_str;}

 public function __add_str(&$_str){
  $new_id_str=count($this->array_str);
  $this->array_str[$new_id_str]=&$_str;
  $id_str=count($this->array_str)-1;
  $str_len=mb_strlen($_str);
  for($i=0;$i<$str_len;$i++){
   $this->array_suffix[]=new segment($this->array_str[$new_id_str],$i,$str_len-$i,array("id_str"=>$id_str));
  }
 }

 public function __add_str2(&$_str,$_id_str){
  $this->array_str[$_id_str]=&$_str;
  $str_len=mb_strlen($_str);
  for($i=0;$i<$str_len;$i++){
   $this->array_suffix[]=new segment($this->array_str[$_id_str],$i,$str_len-$i,array("id_str"=>$_id_str));
  }
 }

 public function __init(){
  $start=microtime(true);
//  usort($this->array_suffix,"usort_segment");
  Tool_segment::quicksort(&$this->array_suffix);
  $time=microtime(true)-$start;
  echo "1 : $time\n";
  $start=microtime(true);
  $res=$this->step2();
  $time=microtime(true)-$start;
  echo "2 : $time\n";
  $start=microtime(true);
  $this->step3($res);
  $time=microtime(true)-$start;
  echo "3 : $time\n";
  $start=microtime(true);
  $this->step4();
  $time=microtime(true)-$start;
  $start=microtime(true);
  echo "4 : $time\n";
  $this->step5();
  $time=microtime(true)-$start;
  echo "5 : $time\n";
  return $this->array_distrib;
 }

 private function step2(){
  $lcps=array();
  $len=count($this->array_suffix);
  for($i=0;$i<$len-1;$i++){
   $lcps[$i]=Tool_segment::get_same_prefix($this->array_suffix[$i],$this->array_suffix[$i+1]);
  }
  $lcps[$i]=0;
  return $lcps;
 }

 private function prefix_ptr($_segment1,$_segment2){
  $len=min($_segment1->__get_len(),$_segment2->__get_len());
  $o1=$_segment1->__get_offset(); $o2=$_segment2->__get_offset();
  for($i=0;$i<$len && ($_segment1->__get_char($i+$o1)==$_segment2->__get_char($i+$o2));$i++);
  return $i;
 }

 public function prefix_ptr2($_segment1,$_segment2){
  $first=$min=0;
  $last=$max=min($_segment1->__get_len(),$_segment2->__get_len());
  $flag;
  while($first<=$last){
    $mid=round(($first+$last)/2,0);
    $prefix_seg1=$_segment1->__get_prefix($mid);
    $prefix_seg2=$_segment2->__get_prefix($mid);
    if($prefix_seg1->__tostring() != $prefix_seg2->__tostring()){
     if($mid<$max) $max=$mid;
     $last=$mid-1;
     $flag=false;
    }
    else{
     if($mid>$min) $min=$mid;
     $first=$mid+1;
     $flag=true;
    }
  }
  return ($flag) ? $mid : $first-1;
 }

 private function step3($_lcps){
  $res=$res2=$return=array();
  $max=count($_lcps);
  $valid=array();

  for($i=0;$i<$max-1;$i++){
   $cpt1=$cpt2=$i;
   if($_lcps[$i]>0){
    $id_str_i=$this->array_suffix[$i]->__get_attribute("id_str");
    if(!isset($res["$i$id_str_i".$_lcps[$i]])){
     $res["$i$id_str_i".$_lcps[$i]]=1;
     $clone=clone $this->array_suffix[$i];
     $clone->__set_attribute("len",$_lcps[$i]);
     $clone->__set_attribute("id_lcps",$i);
     $this->array_repeated[$clone->__tostring()][]=$clone;
    }
    do{
     $cpt1++;
     $id_str_cpt1=$this->array_suffix[$cpt1]->__get_attribute("id_str");
     if(!isset($res["$cpt1$id_str_cpt1".$_lcps[$i]])){
      $res["$cpt1$id_str_cpt1".$_lcps[$i]]=1;
      $clone=clone $this->array_suffix[$cpt1];
      $clone->__set_attribute("len",$_lcps[$i]);
      $clone->__set_attribute("id_lcps",$cpt1);
      $this->array_repeated[$clone->__tostring()][]=$clone;
     }
    }while($_lcps[$i]<=$_lcps[$cpt1]);

    $cpt2--;

    while($_lcps[$i]<=$_lcps[$cpt2]){
     $id_str_cpt2=$this->array_suffix[$cpt2]->__get_attribute("id_str");
     if(!isset($res["$cpt2$id_str_cpt2".$_lcps[$i]])){
      $res["$cpt2$id_str_cpt2".$_lcps[$i]]=1;
      $clone=clone $this->array_suffix[$cpt2];
      $clone->__set_attribute("len",$_lcps[$i]);
      $clone->__set_attribute("id_lcps",$cpt2);
      $this->array_repeated[$clone->__tostring()][]=$clone;
     }
     $cpt2--;
    }

   }
  }

  $start=microtime(true);
//  usort($res,array($this,"step3_usort"));
//  foreach($res as $seg1) $this->array_repeated[$seg1->__tostring()][]=$seg1;
  foreach($this->array_repeated as $array){
    usort($array,array($this,"step3_usort"));
  }

  usort($this->array_repeated,"usort_array_rev_segment");

  $max=count($this->array_repeated);
  for($i=0;$i<$max;$i++){
    usort($this->array_repeated[$i],"usort_array_segment_idstr");
  }

  $time=microtime(true)-$start;
  echo "3.X : $time\n";
 }

 private function step3_usort($i,$j){
  $ii=$i->__get_attribute("id_lcps");$ji=$j->__get_attribute("id_lcps");
  if($ii<$ji) return -1;
  elseif($ii>$ji)return 1;
  else{
   $idi=$i->__get_attribute("id_str");$idj=$j->__get_attribute("id_str");
   if($idi<$idj) return -1;
   elseif($idi>$idj) return 1;
   else return array_segment_usort1($i,$j);
  }
 }


 private function step3_usort_new($i,$j){
  $ii=$i->__get_attribute("id_lcps");$ji=$j->__get_attribute("id_lcps");
  if($ii<$ji) return -1;
  elseif($ii>$ji)return 1;
  else{
   $idi=$i->__get_attribute("id_str");$idj=$j->__get_attribute("id_str");
   if($idi<$idj) return -1;
   elseif($idi>$idj) return 1;
   else{
    $res=array_segment_usort1($i,$j);
    ($res==0) ? usort_array_segment_idstr($i,$j) : $res;
   }
  }
 }



 private function step3_clean(){
  $max=count($this->array_repeated);
  for($i=0;$i<$max;$i++) usort($this->array_repeated[$i],"usort_array_segment_idstr");
 }

 private function step4(){
  $max=count($this->array_repeated);
  for($i=0;$i<$max-1;$i++){
   if($this->array_repeated[$i+1][0]->__does_include_strict($this->array_repeated[$i][0])
      and count($this->array_repeated[$i])==count($this->array_repeated[$i+1])) unset($this->array_repeated[$i]);
  }
  //print_r($this->array_repeated);
  //die();
 }

 private function step5(){
  foreach($this->array_repeated as $repeated){
   foreach($repeated as $segment){
    //$this->array_distrib[$repeated[0]->__tostring()][$segment->__get_attribute("id_str")][]=$segment;
    //$this->array_distrib2[$segment->__get_attribute("id_str")][$repeated[0]->__tostring()][]=$segment;
    $this->array_distrib[$repeated[0]->__tostring()][]=$segment;
   }
  }
  ksort($this->array_distrib);
/*
  uasort($this->array_distrib,array($this,"usort_temp"));

  $copie=$this->array_distrib;
  foreach($copie as $str=>$array_id_str){
   foreach($array_id_str as $id_str=>$array_segment) usort($this->array_distrib[$str][$id_str],"array_segment_usort2");
  }
*/
 }

 //usort_temp($array_segment1,$array_segment2)
 //Comparaison de deux tableaux de segments par leurs tailles
 //$array_segment1[$id_str][$id_rstr]
 private function usort_temp($i,$j){
  return Tool_array::count_recursive($i) - Tool_array::count_recursive($j); 
//  if(Tool_array::count_recursive($i)<Tool_array::count_recursive($j)) return -1;
//  else return (Tool_array::count_recursive($i)>Tool_array::count_recursive($j)) ? 1 : 0;
 }

}

?>
